package com.example.leetcode.trainingcamp.week3.Sunday;

import java.util.Stack;

/**
 * 请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。
 */
public class Test739 {

    // 暴力求解,耗时太长不推荐 1331ms
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] result = new int[len];
        for (int i =0;i<len-1;i++){
            for (int j = i+1;j<len;j++){
                if (temperatures[j]>temperatures[i]){
                    result[i] = j - i;
                    break;
                }
            }
        }
        return result;
    }

    // 单调栈求解 50ms
    public int[] dailyTemperatures2(int[] temperatures) {
        int len = temperatures.length;
        int[] result = new int[len];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0;i<len;i++){
            if (stack.isEmpty()){
                stack.push(i);
            }else {
                while (!stack.isEmpty()){
                    Integer peek = stack.peek();
                    if (temperatures[peek]<temperatures[i]){
                        result[peek] = i - peek;
                        stack.pop();
                    }else {
                        stack.push(i);
                        break;
                    }
                }
                stack.push(i);
            }
        }
        return result;
    }
}


class Demo739{
  public static void main(String[] args) {
    int[] temperatures = {73,74,75,71,69,72,76,73};
    Test739 t = new Test739();
    int[] ints = t.dailyTemperatures2(temperatures);
    for (int i : ints) {
      System.out.printf(i+" ");
    }
  }
}
